package day_2023_7_to_10;

import java.util.LinkedList;
import java.util.List;

/**
 * @author haomin
 * @date 2023/08/01 23:32
 **/
public class Day_8_1 {
    class Solution {
        List<List<Integer>> res = new LinkedList<>();
        public List<List<Integer>> levelOrder(TreeNode root) {
            levelOrderHelper(root, 0);
            return res;
        }
        public void levelOrderHelper(TreeNode root, int k) {
            if (root == null) return;
            if (res.size() <= k) res.add(new LinkedList<>());
            res.get(k).add(root.val);
            levelOrderHelper(root.left, k + 1);
            levelOrderHelper(root.right, k + 1);
        }
    }
    class Solution2 {
        List<List<Integer>> res = new LinkedList<>();
        public List<List<Integer>> levelOrder(TreeNode root) {
            levelOrderHelper(root, 0);
            return res;
        }
        public void levelOrderHelper(TreeNode root, int k) {
            if (root == null) return;
            if (res.size() <= k) res.add(new LinkedList<>());
            if (k % 2 == 0) res.get(k).add(root.val);
            else res.get(k).add(0, root.val);

            levelOrderHelper(root.left, k + 1);
            levelOrderHelper(root.right, k + 1);
        }
    }
}